package 二叉树遍历4种遍历方式;

import 二叉树练习题.BiTNode;
import 二叉树练习题.B如何把一个有序的整数数组放到二叉树中;

import java.util.Stack;

/**
 * 访问顺序：先根节点，再左子树，最后右子树；上图的访问结果为：GDAFEMHZ。
 * <p>
 * 5
 * 3      8
 * 2   4  6   10
 * 1
 */
public class A前序遍历 {

    public static void preOrderTraverse1(BiTNode root) {
        if (root != null) {
            System.out.print(root.data + " ->");
            preOrderTraverse1(root.lchild);
            preOrderTraverse1(root.rchild);
        }
    }

    public static void preOrderTracerse2(BiTNode root) {
        Stack<BiTNode> stack = new Stack<>();

        BiTNode node = root;
        while (node != null || !stack.empty()) {
            if (node != null) {
                System.out.print(node.data + " ->");
                stack.push(node);
                node = node.lchild;
            } else {
                BiTNode tem = stack.pop();
                node = tem.rchild;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 8, 10,11,12,13};

        BiTNode biTNode = B如何把一个有序的整数数组放到二叉树中.arraytotree(arr, 0, arr.length - 1);
        preOrderTraverse1(biTNode);
        System.out.println("  ");
        preOrderTracerse2(biTNode);
    }
}
